/*
 * Generic reference iterator infrastructure. See refs-internal.h for
 * documentation about the design and use of reference iterators.
 */

#include "git-compat-util.h"
#include "refs.h"
#include "refs/refs-internal.h"
#include "iterator.h"

/**
 * Advances the iterator to the next reference.
 *
 * This moves the iterator forward and returns the next
 * reference name. It returns 0 on success, or -1 when
 * there are no more references.
 */
int ref_iterator_advance(struct ref_iterator *ref_iterator)
{
	return ref_iterator->vtable->advance(ref_iterator);
}

/**
 * Peels the reference being iterated on and stores its peeled value
 * in the given peeled variable.
 *
 * The peeled value represents the deepest commit reachable from the
 * current reference. For example, if the reference points to a tag
 * object, the peeled value will be the commit object the tag
 * references.
 *
 * @param ref_iterator The iterator whose reference to peel.
 * @param peeled Where to store the peeled reference value.
 */
int ref_iterator_peel(struct ref_iterator *ref_iterator,
		      struct object_id *peeled)
{
	return ref_iterator->vtable->peel(ref_iterator, peeled);
}

/**
 * Aborts iteration and frees the ref_iterator.
 *
 * This function should free the iterator and release any associated
 * resources. Callers should not call this function after the iterator
 * reaches EOF. They should just free the iterator normally.
 */
int ref_iterator_abort(struct ref_iterator *ref_iterator)
{
	return ref_iterator->vtable->abort(ref_iterator);
}

/**
 * Initializes a base ref iterator structure.
 *
 * This sets up the basic fields of the ref iterator structure pointed
 * to by iter, including setting the vtable and ordering flag.
 *
 * @param iter The ref iterator structure to initialize.
 * @param vtable The vtable specifying iterator operations.
 * @param ordered Whether to iterate entries in order by name.
 */
void base_ref_iterator_init(struct ref_iterator *iter,
			    struct ref_iterator_vtable *vtable,
			    int ordered)
{
	iter->vtable = vtable;
	iter->ordered = !!ordered;
	iter->refname = NULL;
	iter->oid = NULL;
	iter->flags = 0;
}

/**
 * Frees a base ref iterator structure.
 *
 * This releases any resources associated with the given base ref
 * iterator structure pointed to by iter, including calling the
 * vtable's free function if set.
 *
 * @param iter The base ref iterator to free.
 */
void base_ref_iterator_free(struct ref_iterator *iter)
{
	/* Help make use-after-free bugs fail quickly: */
	iter->vtable = NULL;
	free(iter);
}

struct empty_ref_iterator {
	struct ref_iterator base;
};

/**
 * Advances the empty ref iterator. This is a no-op function that
 * immediately returns ITER_DONE to indicate EOF.
 *
 * @param ref_iterator The empty ref iterator.
 * @return ITER_DONE to indicate EOF.
 */
static int empty_ref_iterator_advance(struct ref_iterator *ref_iterator)
{
	return ref_iterator_abort(ref_iterator);
}

/**
 * Peels the empty ref iterator. This is a no-op function that
 * triggers a BUG() since peeling should not be called on an
 * empty iterator.
 *
 * @param ref_iterator The empty ref iterator.
 * @param peeled Pointer to store the peeled object ID. Not used.
 * @return Nothing, triggers BUG().
 */
static int empty_ref_iterator_peel(struct ref_iterator *ref_iterator UNUSED,
				   struct object_id *peeled UNUSED)
{
	BUG("peel called for empty iterator");
}

/**
 * Aborts the empty ref iterator.
 *
 * @param ref_iterator The empty ref iterator to abort.
 * @return ITER_DONE to indicate the iterator was aborted.
 */
static int empty_ref_iterator_abort(struct ref_iterator *ref_iterator)
{
	base_ref_iterator_free(ref_iterator);
	return ITER_DONE;
}

static struct ref_iterator_vtable empty_ref_iterator_vtable = {
	.advance = empty_ref_iterator_advance,
	.peel = empty_ref_iterator_peel,
	.abort = empty_ref_iterator_abort,
};

/**
 * Returns an empty ref_iterator.
 *
 * This iterator has no entries and immediately indicates EOF.
 * It is primarily used for boundary conditions.
 */
struct ref_iterator *empty_ref_iterator_begin(void)
{
	struct empty_ref_iterator *iter = xcalloc(1, sizeof(*iter));
	struct ref_iterator *ref_iterator = &iter->base;

	base_ref_iterator_init(ref_iterator, &empty_ref_iterator_vtable, 1);
	return ref_iterator;
}

/**
 * Checks if the given ref_iterator is an empty iterator.
 *
 * @param ref_iterator The ref_iterator to check.
 * @return 1 if the iterator is empty, 0 otherwise.
 */
int is_empty_ref_iterator(struct ref_iterator *ref_iterator)
{
	return ref_iterator->vtable == &empty_ref_iterator_vtable;
}

struct merge_ref_iterator {
	struct ref_iterator base;

	struct ref_iterator *iter0, *iter1;

	ref_iterator_select_fn *select;
	void *cb_data;

	/*
	 * A pointer to iter0 or iter1 (whichever is supplying the
	 * current value), or NULL if advance has not yet been called.
	 */
	struct ref_iterator **current;
};

/**
 * Advance the merge ref iterator to the next entry.
 *
 * This handles advancing the underlying iterators and
 * calling the selection callback to determine which
 * iterator should supply the next entry.
 */
static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator)
{
	struct merge_ref_iterator *iter =
		(struct merge_ref_iterator *)ref_iterator;
	int ok;

	if (!iter->current) {
		/* Initialize: advance both iterators to their first entries */
		if ((ok = ref_iterator_advance(iter->iter0)) != ITER_OK) {
			iter->iter0 = NULL;
			if (ok == ITER_ERROR)
				goto error;
		}
		if ((ok = ref_iterator_advance(iter->iter1)) != ITER_OK) {
			iter->iter1 = NULL;
			if (ok == ITER_ERROR)
				goto error;
		}
	} else {
		/*
		 * Advance the current iterator past the just-used
		 * entry:
		 */
		if ((ok = ref_iterator_advance(*iter->current)) != ITER_OK) {
			*iter->current = NULL;
			if (ok == ITER_ERROR)
				goto error;
		}
	}

	/* Loop until we find an entry that we can yield. */
	while (1) {
		struct ref_iterator **secondary;
		enum iterator_selection selection =
			iter->select(iter->iter0, iter->iter1, iter->cb_data);

		if (selection == ITER_SELECT_DONE) {
			return ref_iterator_abort(ref_iterator);
		} else if (selection == ITER_SELECT_ERROR) {
			ref_iterator_abort(ref_iterator);
			return ITER_ERROR;
		}

		if ((selection & ITER_CURRENT_SELECTION_MASK) == 0) {
			iter->current = &iter->iter0;
			secondary = &iter->iter1;
		} else {
			iter->current = &iter->iter1;
			secondary = &iter->iter0;
		}

		if (selection & ITER_SKIP_SECONDARY) {
			if ((ok = ref_iterator_advance(*secondary)) != ITER_OK) {
				*secondary = NULL;
				if (ok == ITER_ERROR)
					goto error;
			}
		}

		if (selection & ITER_YIELD_CURRENT) {
			iter->base.refname = (*iter->current)->refname;
			iter->base.oid = (*iter->current)->oid;
			iter->base.flags = (*iter->current)->flags;
			return ITER_OK;
		}
	}

error:
	ref_iterator_abort(ref_iterator);
	return ITER_ERROR;
}

/**
 * Peel the current reference from the merge ref iterator by delegating
 * to the peel method of the current underlying ref iterator.
 *
 * @param ref_iterator the merge ref iterator
 * @param peeled output parameter to store the peeled reference
 * @return the return code of the peel operation (ITER_OK, ITER_ERROR)
 */
static int merge_ref_iterator_peel(struct ref_iterator *ref_iterator,
				   struct object_id *peeled)
{
	struct merge_ref_iterator *iter =
		(struct merge_ref_iterator *)ref_iterator;

	if (!iter->current) {
		BUG("peel called before advance for merge iterator");
	}
	return ref_iterator_peel(*iter->current, peeled);
}

/**
 * Abort the merge ref iterator by aborting both underlying iterators.
 *
 * @param ref_iterator the merge ref iterator to abort
 * @return ITER_DONE if both underlying iterators were successfully aborted,
 *   ITER_ERROR otherwise
 */
static int merge_ref_iterator_abort(struct ref_iterator *ref_iterator)
{
	struct merge_ref_iterator *iter =
		(struct merge_ref_iterator *)ref_iterator;
	int ok = ITER_DONE;

	if (iter->iter0) {
		if (ref_iterator_abort(iter->iter0) != ITER_DONE)
			ok = ITER_ERROR;
	}
	if (iter->iter1) {
		if (ref_iterator_abort(iter->iter1) != ITER_DONE)
			ok = ITER_ERROR;
	}
	base_ref_iterator_free(ref_iterator);
	return ok;
}

static struct ref_iterator_vtable merge_ref_iterator_vtable = {
	.advance = merge_ref_iterator_advance,
	.peel = merge_ref_iterator_peel,
	.abort = merge_ref_iterator_abort,
};

/**
 * Begin a merged ref iterator that iterates over two ref iterators in order,
 * calling a callback function to select the appropriate ref from the two
 * iterators for each iteration.
 *
 * @param ordered whether to iterate in order by refname across both iterators
 * @param iter0 the first ref iterator
 * @param iter1 the second ref iterator
 * @param select callback function to select the appropriate ref
 * @param cb_data user data to pass to the callback function
 * @return the merged ref iterator
 */
struct ref_iterator *merge_ref_iterator_begin(
		int ordered,
		struct ref_iterator *iter0, struct ref_iterator *iter1,
		ref_iterator_select_fn *select, void *cb_data)
{
	struct merge_ref_iterator *iter = xcalloc(1, sizeof(*iter));
	struct ref_iterator *ref_iterator = &iter->base;

	/*
	 * We can't do the same kind of is_empty_ref_iterator()-style
	 * optimization here as overlay_ref_iterator_begin() does,
	 * because we don't know the semantics of the select function.
	 * It might, for example, implement "intersect" by passing
	 * references through only if they exist in both iterators.
	 */

	base_ref_iterator_init(ref_iterator, &merge_ref_iterator_vtable, ordered);
	iter->iter0 = iter0;
	iter->iter1 = iter1;
	iter->select = select;
	iter->cb_data = cb_data;
	iter->current = NULL;
	return ref_iterator;
}

/*
 * A ref_iterator_select_fn that overlays the items from front on top
 * of those from back (like loose refs over packed refs). See
 * overlay_ref_iterator_begin().
 */
/**
 * Select function for overlay_ref_iterator_begin() to overlay refs.
 * Compares names of refs from front and back iterators and selects
 * the appropriate one to return, skipping duplicates. Gives priority
 * to refs from front iterator.
 */
static enum iterator_selection
overlay_iterator_select(
		struct ref_iterator *front, struct ref_iterator *back,
		void *cb_data UNUSED)
{
	int cmp;

	if (!back)
		return front ? ITER_SELECT_0 : ITER_SELECT_DONE;
	else if (!front)
		return ITER_SELECT_1;

	cmp = strcmp(front->refname, back->refname);

	if (cmp < 0)
		return ITER_SELECT_0;
	else if (cmp > 0)
		return ITER_SELECT_1;
	else
		return ITER_SELECT_0_SKIP_1;
}

/**
 * Begin an overlay ref iterator that iterates over the entries from
 * front and back iterators, skipping duplicates. Entries from front
 * take precedence over entries from back if they have the same name.
 *
 * @param front the front ref iterator
 * @param back the back ref iterator
 * @return a new overlay ref iterator
 */
struct ref_iterator *overlay_ref_iterator_begin(
		struct ref_iterator *front, struct ref_iterator *back)
{
	/*
	 * Optimization: if one of the iterators is empty, return the
	 * other one rather than incurring the overhead of wrapping
	 * them.
	 */
	if (is_empty_ref_iterator(front)) {
		ref_iterator_abort(front);
		return back;
	} else if (is_empty_ref_iterator(back)) {
		ref_iterator_abort(back);
		return front;
	} else if (!front->ordered || !back->ordered) {
		BUG("overlay_ref_iterator requires ordered inputs");
	}

	return merge_ref_iterator_begin(1, front, back,
					overlay_iterator_select, NULL);
}

struct prefix_ref_iterator {
	struct ref_iterator base;

	struct ref_iterator *iter0;
	char *prefix;
	int trim;
};

/* Return -1, 0, 1 if refname is before, inside, or after the prefix. */
/**
 * Compare refname to prefix.
 * Returns -1 if refname is before prefix,
 * 0 if refname is inside prefix,
 * 1 if refname is after prefix.
 */
static int compare_prefix(const char *refname, const char *prefix)
{
	while (*prefix) {
		if (*refname != *prefix)
			return ((unsigned char)*refname < (unsigned char)*prefix) ? -1 : +1;

		refname++;
		prefix++;
	}

	return 0;
}

/**
 * Advances the prefix ref iterator to the next ref.
 *
 * @param ref_iterator the prefix ref iterator
 * @return ITER_OK if a ref was found, ITER_DONE if iteration finished,
 *   ITER_ERROR if there was an error
 */
static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator)
{
	struct prefix_ref_iterator *iter =
		(struct prefix_ref_iterator *)ref_iterator;
	int ok;

	while ((ok = ref_iterator_advance(iter->iter0)) == ITER_OK) {
		int cmp = compare_prefix(iter->iter0->refname, iter->prefix);

		if (cmp < 0)
			continue;

		if (cmp > 0) {
			/*
			 * If the source iterator is ordered, then we
			 * can stop the iteration as soon as we see a
			 * refname that comes after the prefix:
			 */
			if (iter->iter0->ordered) {
				ok = ref_iterator_abort(iter->iter0);
				break;
			} else {
				continue;
			}
		}

		if (iter->trim) {
			/*
			 * It is nonsense to trim off characters that
			 * you haven't already checked for via a
			 * prefix check, whether via this
			 * `prefix_ref_iterator` or upstream in
			 * `iter0`). So if there wouldn't be at least
			 * one character left in the refname after
			 * trimming, report it as a bug:
			 */
			if (strlen(iter->iter0->refname) <= iter->trim)
				BUG("attempt to trim too many characters");
			iter->base.refname = iter->iter0->refname + iter->trim;
		} else {
			iter->base.refname = iter->iter0->refname;
		}

		iter->base.oid = iter->iter0->oid;
		iter->base.flags = iter->iter0->flags;
		return ITER_OK;
	}

	iter->iter0 = NULL;
	if (ref_iterator_abort(ref_iterator) != ITER_DONE)
		return ITER_ERROR;
	return ok;
}

/**
 * Peel a reference for the prefix ref iterator by peeling the
 * reference from the underlying base iterator.
 *
 * @param ref_iterator the prefix ref iterator
 * @param peeled output peeled reference object ID
 * @return result of peeling on base iterator
 */
static int prefix_ref_iterator_peel(struct ref_iterator *ref_iterator,
				    struct object_id *peeled)
{
	struct prefix_ref_iterator *iter =
		(struct prefix_ref_iterator *)ref_iterator;

	return ref_iterator_peel(iter->iter0, peeled);
}

/**
 * Abort iteration for a prefix ref iterator.
 *
 * Aborts the iteration for the given prefix ref iterator by aborting
 * the underlying base iterator if it exists.
 *
 * @param ref_iterator the prefix ref iterator to abort
 * @return ITER_DONE if successfully aborted, ITER_ERROR otherwise
 */
static int prefix_ref_iterator_abort(struct ref_iterator *ref_iterator)
{
	struct prefix_ref_iterator *iter =
		(struct prefix_ref_iterator *)ref_iterator;
	int ok = ITER_DONE;

	if (iter->iter0)
		ok = ref_iterator_abort(iter->iter0);
	free(iter->prefix);
	base_ref_iterator_free(ref_iterator);
	return ok;
}

static struct ref_iterator_vtable prefix_ref_iterator_vtable = {
	.advance = prefix_ref_iterator_advance,
	.peel = prefix_ref_iterator_peel,
	.abort = prefix_ref_iterator_abort,
};

/**
 * Create a new prefix ref iterator.
 *
 * This wraps an existing ref iterator, only yielding references
 * that begin with a given prefix.
 *
 * @param iter0 the base iterator to wrap
 * @param prefix only yield refs beginning with this prefix
 * @param trim trim this many characters from the beginning of yielded ref names
 * @return the new prefix ref iterator
 */
struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,
					       const char *prefix,
					       int trim)
{
	struct prefix_ref_iterator *iter;
	struct ref_iterator *ref_iterator;

	if (!*prefix && !trim)
		return iter0; /* optimization: no need to wrap iterator */

	CALLOC_ARRAY(iter, 1);
	ref_iterator = &iter->base;

	base_ref_iterator_init(ref_iterator, &prefix_ref_iterator_vtable, iter0->ordered);

	iter->iter0 = iter0;
	iter->prefix = xstrdup(prefix);
	iter->trim = trim;

	return ref_iterator;
}

struct ref_iterator *current_ref_iter = NULL;

/**
 * Iterate over the references in the given repository and ref_iterator,
 * calling the given callback function for each reference.
 *
 * @param r the repository to iterate over
 * @param iter the ref_iterator to use
 * @param fn the callback function to call for each reference
 * @param cb_data extra data to pass to the callback function
 * @return 0 on success, non-zero callback return value on error
 */
int do_for_each_repo_ref_iterator(struct repository *r,
				  struct ref_iterator *iter,
				  each_repo_ref_fn fn, void *cb_data)
{
	int retval = 0, ok;
	struct ref_iterator *old_ref_iter = current_ref_iter;

	current_ref_iter = iter;
	while ((ok = ref_iterator_advance(iter)) == ITER_OK) {
		retval = fn(r, iter->refname, iter->oid, iter->flags, cb_data);
		if (retval) {
			/*
			 * If ref_iterator_abort() returns ITER_ERROR,
			 * we ignore that error in deference to the
			 * callback function's return value.
			 */
			ref_iterator_abort(iter);
			goto out;
		}
	}

out:
	current_ref_iter = old_ref_iter;
	if (ok == ITER_ERROR)
		return -1;
	return retval;
}
